/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        295.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/17 21:33
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//数据流的中位数
#include "../header.h"
class MedianFinder {
    priority_queue<int> lo;
    priority_queue<int,vector<int>,greater<int>> hi;
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        lo.push(num);
        hi.push(lo.top());
        lo.pop();
        if (lo.size() < hi.size()){
            lo.push(hi.top());
            hi.pop();
        }
    }

    double findMedian() {
        return lo.size() > hi.size() ? (double )lo.top() : (lo.top() + hi.top()) * 0.5;
    }
};